/* 建立中序线索二叉树 */
#include <iostream>
#include "InThreadBiTreefun.h"
using namespace std;

// 为中序线索二叉树添加线索
void InTh(TNode *&p, TNode *&pre)
{
  // 结点不为空
  if (p != NULL)
  {
    /* 为左子树添加线索 */
    InTh(p->lchild, pre);
    
    /* 为当前结点添加线索 */
    
    // 如果结点不存在左孩子结点
    if (p->lchild == NULL)
    {
      p->lchild = pre; // 指向前驱结点
      p->ltag = 1; // 更改标记
    }
    
    // 如果结点不存在右孩子结点
    if (pre != NULL && pre->rchild == NULL)
    {
      pre->rchild = p;
      pre->rtag = 1; // 更改标记
    }
    
    // 更改前驱结点
    pre = p;
    
    /* 为右子树添加线索 */
    InTh(p->rchild, pre);
  }
}

// 构建中序线索二叉树
iTree create_iTree()
{
  // 接收用户输入
  char x;
  cin >> x;
  
  // 持续接收用户输入，直到遇到终止符
  if (x != '#')
  {
    // 创建结点
    TNode *T = new TNode;
    T->data = x;
    
    // 创建左子树
    T->lchild = create_iTree();
    
    // 创建右子树
    T->rchild = create_iTree();
    return T;
  }
  return NULL;
}
